Sprite 1984 - 1993/Sprite 1984 - 1993.iso/src/lib/include/RCS/hash.h,v

Text File | 1991-07-27 | 4.6 KB | 198 lines

head     1.3;
branch   ;
access   ;
symbols  ;
locks    ; strict;
comment  @ * @;


1.3
date     89.06.23.11.29.46;  author rab;  state Exp;
branches ;
next     1.2;

1.2
date     88.06.29.14.57.27;  author ouster;  state Exp;
branches ;
next     1.1;

1.1
date     88.06.21.09.36.52;  author ouster;  state Exp;
branches ;
next     ;


desc
@@


1.3
log
@*** empty log message ***
@
text
@/* hash.h --
 *
 *     This file contains definitions used by the hash module,
 *     which maintains hash tables.
 *
 * Copyright 1986, 1988 Regents of the University of California
 * Permission to use, copy, modify, and distribute this
 * software and its documentation for any purpose and without
 * fee is hereby granted, provided that the above copyright
 * notice appear in all copies.  The University of California
 * makes no representations about the suitability of this
 * software for any purpose.  It is provided "as is" without
 * express or implied warranty.
 *
 * $Header: /sprite/src/lib/include/RCS/hash.h,v 1.2 88/06/29 14:57:27 ouster Exp Locker: rab $ SPRITE (Berkeley)
 */


#ifndef    _HASH
#define    _HASH

#ifndef _LIST
#include <list.h>
#endif
#ifndef _SPRITE
#include <sprite.h>
#endif

/*
 * The following defines one entry in the hash table.
 */

typedef struct Hash_Entry {
    List_Links          links;        /* Used to link together all the
                         * entries associated with the same
                     * bucket. */
    ClientData          clientData;    /* Arbitrary piece of data associated
                         * with key. */
    union {
    Address     ptr;            /* One-word key value to identify
                     * entry. */
    int words[1];            /* N-word key value.  Note: the actual
                     * size may be longer if necessary to
                     * hold the entire key. */
    char      name[4];        /* Text name of this entry.  Note: the
                     * actual size may be longer if
                     * necessary to hold the whole string.
                     * This MUST be the last entry in the
                     * structure!!! */
    } key;
} Hash_Entry;

/*
 * A hash table consists of an array of pointers to hash
 * lists.  Tables can be organized in either of three ways, depending
 * on the type of comparison keys:
 *
 *    Strings:      these are NULL-terminated; their address
 *              is passed to HashFind as a (char *).
 *    Single-word keys: these may be anything, but must be passed
 *              to Hash_Find as an Address.
 *    Multi-word keys:  these may also be anything; their address
 *              is passed to HashFind as an Address.
 *
 *    Single-word keys are fastest, but most restrictive.
 */

#define HASH_STRING_KEYS    0
#define HASH_ONE_WORD_KEYS    1

typedef struct Hash_Table {
    List_Links     *bucketPtr;    /* Pointer to array of List_Links, one
                     * for each bucket in the table. */
    int     size;        /* Actual size of array. */
    int     numEntries;    /* Number of entries in the table. */
    int     downShift;    /* Shift count, used in hashing function. */
    int     mask;        /* Used to select bits for hashing. */
    int     keyType;    /* Type of keys used in table:
                     * HASH_STRING_KEYS, HASH_ONE-WORD_KEYS,
                 * or >1 menas keyType gives number of words
                 * in keys.
                 */
} Hash_Table;

/*
 * The following structure is used by the searching routines
 * to record where we are in the search.
 */

typedef struct Hash_Search {
    Hash_Table  *tablePtr;    /* Table being searched. */
    int     nextIndex;    /* Next bucket to check (after current). */
    Hash_Entry     *hashEntryPtr;    /* Next entry to check in current bucket. */
    List_Links    *hashList;    /* Hash chain currently being checked. */
} Hash_Search;

/*
 * Macros.
 */

/*
 * ClientData Hash_GetValue(h)
 *     Hash_Entry *h;
 */

#define Hash_GetValue(h) ((h)->clientData)

/*
 * Hash_SetValue(h, val);
 *     HashEntry *h;
 *     char *val;
 */

#define Hash_SetValue(h, val) ((h)->clientData = (ClientData) (val))

/*
 * Hash_Size(n) returns the number of words in an object of n bytes
 */

#define    Hash_Size(n)    (((n) + sizeof (int) - 1) / sizeof (int))

/*
 * The following procedure declarations and macros
 * are the only things that should be needed outside
 * the implementation code.
 */

extern Hash_Entry *    Hash_CreateEntry();
extern void        Hash_DeleteTable();
extern void        Hash_DeleteEntry();
extern void        Hash_DeleteTable();
extern Hash_Entry *    Hash_EnumFirst();
extern Hash_Entry *    Hash_EnumNext();
extern Hash_Entry *    Hash_FindEntry();
extern void        Hash_InitTable();
extern void        Hash_PrintStats();

#endif /* _HASH */
@


1.2
log
@Add ifdefs so that file can't be processed twice.
@
text
@d15 1
a15 1
 * $Header: hash.h,v 1.1 88/06/21 09:36:52 ouster Exp $ SPRITE (Berkeley)
d138 1
a138 1
#endif _HASH
@


1.1
log
@Initial revision
@
text
@d15 1
a15 1
 * $Header: hash.h,v 1.1 88/06/20 09:30:26 ouster Exp $ SPRITE (Berkeley)
@